import java.util.HashSet;
import java.util.Set;

//链表经典题目：（1）判环（2）找链表中环的入口（3）找链表中倒数第N个结点
//（1）判环
//https://leetcode.cn/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-100-liked
public class Test {
    public static void main(String[] args) {
        //
    }
}
class ListNode{
    ListNode next = new ListNode();
}

//方法一：记录每个结点是否出现过（通过√）
class Solution1 {
    public boolean hasCycle(ListNode head) {
        ListNode cur = head;
        if(cur == null||cur.next == null){
            return false;
        }
        Set<ListNode> set = new HashSet<ListNode>();
        while(cur != null){
            /*if(set.add(cur)) cur = cur.next;
            else return false;*/
            if(set.add(cur)){
                cur = cur.next;
            }else {
                return true;
            }
        }
        return false;
    }
}


//方法二：“龟兔赛跑”——快慢指针，相遇（通过√）
class Solution2 {
    public boolean hasCycle(ListNode head) {
        if(head == null||head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            if(fast == slow){
                return true;
            }
            slow  = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}
